home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 501-525 / disk_519 / avlsort / avlsort.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  17KB  |  656 lines
  1. /*---------------------------------------------------------------------------
  2.  * AVLSORT From,To,COLSTART/k,WIDTH/k,TABSTOP/k,CASE/s,REVERSE/s,STRIP/s
  3.  *
  4.  * Amiga Usage:
  5.  *    From         input file (default stdin)
  6.  *    To           output file (default stdout)
  7.  *    COLSTART nn  start at column nn (default is 1)
  8.  *    WIDTH nn     width of sort field (default is entire line)
  9.  *    TABSTOP nn   expand tabs (default is no expansion)
  10.  *    CASE         case sensitive (default case insensitive)
  11.  *    REVERSE      sort in reverse order
  12.  *    STRIP        strip trailing white space
  13.  *    OPT T|C|R|S  same as TABSTOP 8 | CASE | REVERSE | STRIP
  14.  *
  15.  * Copyright © 1990, 1991 by Robert L. Pyron. All Rights Reserved.
  16.  * This program may be freely distributed, provided that all the files in
  17.  * this archive are included.  Bug fixes and improvements are welcome,
  18.  * please send these to me on BIX (rpyron).
  19.  *
  20.  * Version 1.1, Robert L. Pyron, 19 June 1991
  21.  *
  22.  * This is an update to AVLSORT.LZH, posted previously on BIX. There are
  23.  * several bug fixes and an algorithm improvement:
  24.  *
  25.  *    -- Better tracking of memory
  26.  *    -- Check for control-C, -D, -E, and -F
  27.  *    -- Split into several source files
  28.  *    -- Identical lines are now placed in a linked list
  29.  *
  30.  *---------------------------------------------------------------------------
  31.  */
  32.  
  33. #include <exec/types.h>
  34. #include <exec/nodes.h>
  35. #include <exec/lists.h>
  36. #include <proto/exec.h>
  37. #include <Arp/ArpBase.h>
  38.  
  39. #include <ctype.h>
  40. #include <stdio.h>
  41. #include <stdlib.h>
  42. #include <string.h>
  43. #include <setjmp.h>
  44.  
  45. #include "avltree.h"
  46. #include "getline.h"
  47. #include "isatty.h"
  48. #include "mem.h"
  49.  
  50. /*---------------------------------------------------------------------------
  51.  * ARP support
  52.  *---------------------------------------------------------------------------
  53.  */
  54.  
  55. extern struct ArpBase *ArpBase;
  56.  
  57.     /* Template and Extended Help for GADS(), from ARP */
  58.  
  59. char *CLI_Template =    "From,To,COL=COLSTART/k,WID=WIDTH/k,"
  60.             "TAB=TABS=TABSTOP/k,CASE/s,R=REVERSE/s,"
  61.             "STRIP/s,OPT/k";
  62. char *CLI_Help =
  63.     "Usage:\n"
  64.     "  From         input file (default stdin)\n"
  65.     "  To           output file (default stdout)\n"
  66.     "  COLSTART nn  start at column nn (default is 1)\n"
  67.     "  WIDTH nn     width of sort field (default is entire line)\n"
  68.     "  TABSTOP nn   expand tabs (default is no expansion)\n"
  69.     "  CASE         case sensitive (default case insensitive)\n"
  70.     "  REVERSE      sort in reverse order\n" ;
  71.  
  72. /*---------------------------------------------------------------------------
  73.  * Typedefs and defines
  74.  *---------------------------------------------------------------------------
  75.  */
  76.  
  77. #define    ISSPACE(c)    (isascii(c) && isspace(c))
  78.  
  79. #define FALSE    0
  80. #define TRUE    1
  81. #define    TEXTMAX    32767
  82.  
  83. #define    BREAKFLAGS    (SIGBREAKF_CTRL_C | SIGBREAKF_CTRL_D | \
  84.              SIGBREAKF_CTRL_E | SIGBREAKF_CTRL_F )
  85.  
  86. typedef    unsigned char    UCHAR;
  87. typedef    unsigned short    USHORT;
  88. typedef    unsigned long    ULONG;
  89. typedef    UCHAR        *PCHAR;
  90. typedef    void        *PVOID;
  91. typedef    struct MinNode    MINNODE;
  92.  
  93. typedef struct _MYNODE
  94. {
  95.     union    {
  96.         AVLNODE    avlnode;
  97.         MINNODE    minnode;
  98.         }    v;
  99.     PCHAR        text;
  100.     ULONG        textlen;
  101.     struct List    chain;
  102. } MYNODE;
  103. typedef MYNODE    *PNODE;
  104. #define    SZOF_MYNODE    sizeof(MYNODE)
  105.  
  106. typedef int (*PFNCOMPARE) (const char *, const char *, unsigned int);
  107.  
  108. /*---------------------------------------------------------------------------
  109.  * Prototypes
  110.  *---------------------------------------------------------------------------
  111.  */
  112.  
  113. static    void      handlebreak (LONG mask);
  114. static    FILE      *redirect (char *filename, char *mode, FILE *oldfp,
  115.                 int errlevel );
  116.  
  117. static    int      __regargs cmdparse (int argc, char **argv);
  118. static    MYNODE *  __regargs newnode (PCHAR text, ULONG textlen);
  119. static    void      __regargs printtree (MYNODE * p);
  120.  
  121. static    int      __regargs cmprtc (void *keyP, AVLNODE *nodeP);
  122. static    AVLNODE * __regargs mknode (AVLTREE *treeP, void *keyP, void *dataP,
  123.                     AVLNODE *enodeP);
  124. static    void      __regargs rmnode (AVLTREE *treeP, AVLNODE *nodeP);
  125.  
  126. /*---------------------------------------------------------------------------
  127.  * Global data
  128.  *---------------------------------------------------------------------------
  129.  */
  130.  
  131.     /*
  132.      * User may specify the following parameters on command line:
  133.      */
  134.  
  135. char *infile = NULL;        /* input file name, default stdin */
  136. char *outfile = NULL;        /* output file name, default stdout */
  137. long colstart = 0;        /* start column, default 1 */
  138. long colwidth = TEXTMAX;    /* width, default full line */
  139. long tabstop = 0;        /* translate tabs, default no translate */
  140. int caseflag = 0;        /* case sensitivity, default off */
  141. int reverseflag = 0;        /* reverse sort, default off */
  142. int stripflag = 0;        /* strip trailing blanks, default off */
  143.  
  144.     /*
  145.      * This is our AVL tree.
  146.      */
  147.  
  148. AVLTREE avlTree =
  149. {
  150.     NULL,        /* ptr to root node */
  151.     cmprtc,        /* compare node to arbitrary data */
  152.     mknode,        /* create node */
  153.     rmnode        /* destroy node */
  154. };
  155. #define    avlRoot    ((MYNODE *)avlTree.t_rootP)
  156.  
  157.     /*
  158.      * Pointer to string comparison function. If case sensitivity
  159.      * is off (default), use strnicmp().  Otherwise use strncmp().
  160.      */
  161.  
  162. PFNCOMPARE pfnCompare = (PFNCOMPARE) strnicmp;
  163.  
  164.     /*
  165.      * jmp_buf struct for handlebreak().
  166.      */
  167.  
  168. jmp_buf    break_jmp_buf;
  169.  
  170.  
  171. /*---------------------------------------------------------------------------
  172.  *---------------------------------------------------------------------------
  173.  */
  174.  
  175. static    void    handlebreak (LONG mask)
  176. {
  177.     if (mask)
  178.     {
  179.         fflush (stdout);
  180.         fflush (stderr);
  181.         fprintf (stderr, "*** BREAK\n");
  182.         longjmp (break_jmp_buf, 20);
  183.     }
  184. }
  185.  
  186. /*---------------------------------------------------------------------------
  187.  * Notice int return type, we are returning a value to Arp startup code.
  188.  *---------------------------------------------------------------------------
  189.  */
  190.  
  191. int 
  192. main (int argc, char **argv)
  193. {
  194.     long        line_number;
  195.     MYNODE *    pnew;
  196.     int        status;
  197.     register PCHAR    textbuf;
  198.     int        textlen;
  199.  
  200.     /*--------------------------------------
  201.      * Set up jump buffer for handlebreak().
  202.      *--------------------------------------
  203.      */
  204.  
  205.     if (status = setjmp(break_jmp_buf))
  206.         goto hell;
  207.     status = 20;        /* assume the worst */
  208.  
  209.     /*-------------------------------
  210.      * Get options from command line.
  211.      *-------------------------------
  212.      */
  213.  
  214.     if (cmdparse (argc, argv))
  215.         goto hell;
  216.  
  217.     if (--colstart < 0)
  218.         colstart = 0;    /* convert to zero-based */
  219.     if (colwidth <= 0)
  220.         colwidth = TEXTMAX;
  221.     if (caseflag)
  222.         pfnCompare = (PFNCOMPARE) strncmp;
  223.  
  224.     if (infile && !*infile)
  225.         infile = NULL;
  226.     else if (infile && strcmp (infile, "-") == 0)
  227.         infile = NULL;
  228.     else if (infile && strcmp (infile, "=") == 0)
  229.         infile = NULL;
  230.  
  231.     if (outfile && !*outfile)
  232.         outfile = infile;
  233.     else if (outfile && strcmp (outfile, "-") == 0)
  234.         outfile = NULL;
  235.     else if (outfile && strcmp (outfile, "=") == 0)
  236.         outfile = infile;
  237.  
  238.     /*--------------------------------------------
  239.      * Redirect stdin to named file, if specified.
  240.      *--------------------------------------------
  241.      */
  242.  
  243.     if (infile)
  244.         redirect (infile, "r", stdin, 20);
  245.     if (!isatty(fileno(stdin)))
  246.         setvbuf(stdin,NULL,_IOFBF,16384);
  247.  
  248.     /*-----------------------
  249.      * Allocate line buffers.
  250.      *-----------------------
  251.      */
  252.  
  253.     if ((textbuf = ArpAlloc (TEXTMAX+1)) == NULL)
  254.     {
  255.         fprintf (stderr, "?? Out of memory\n");
  256.         goto hell;
  257.     }
  258.  
  259.     /*----------------------------------
  260.      * Read file; put each line in tree.
  261.      *----------------------------------
  262.      */
  263.  
  264.     line_number = 0;
  265.     while ((textlen = getline(textbuf,TEXTMAX,tabstop,stdin)) >= 0)
  266.     {
  267.         /*---------------------------------------------
  268.          * Call ARP function to check for break signal.
  269.          *---------------------------------------------
  270.          */
  271.         CheckBreak (BREAKFLAGS, handlebreak);
  272.  
  273.         if (stripflag)
  274.         {
  275.             while (textlen && ISSPACE(textbuf[textlen-1]) )
  276.                 textbuf[--textlen] = '\0';
  277.         }
  278.  
  279.         if (!(pnew = newnode(textbuf, (ULONG)textlen)))
  280.             goto hell;
  281.  
  282.         switch (avlinsert (&avlTree, pnew, NULL))
  283.         {
  284.         case -1:    /* error */
  285.             fprintf (stderr, "?? Cannot insert line (%lu): %s\n",
  286.                  line_number, pnew->text);
  287.             goto hell;
  288.  
  289.         case 0:        /* success */
  290.             break;
  291.  
  292.         case 1:        /* duplicate key */
  293.             fprintf (stderr, "?? Duplicate key (%lu): %s\n",
  294.                  line_number, pnew->text);
  295.             goto hell;
  296.  
  297.         default:
  298.             fprintf (stderr, "?? Unknown return from avlinsert()\n");
  299.             goto hell;
  300.         }
  301.  
  302.         line_number++;
  303.     }
  304.  
  305.     /*---------------------------------------------
  306.      * Print file.
  307.      * Redirect stdout to named file, if specified.
  308.      * Close stdin because may be same file.
  309.      *---------------------------------------------
  310.      */
  311.  
  312.     fclose (stdin);
  313.     if (outfile)
  314.         redirect (outfile, "w", stdout, 20);
  315.     if (!isatty(fileno(stdout)))
  316.         setvbuf(stdout,NULL,_IOFBF,16384);
  317.  
  318.     printtree (avlRoot);
  319.     status = 0;        /* ok */
  320.  
  321. hell:
  322.     myfreeall ();
  323.     return (status);
  324. }
  325.  
  326. /*--------------------------------------------------------------------
  327.  * We link with S. Vigna's ARP startup code, which calls GADS() for us
  328.  * and returns the result as argv[].  We can ignore argc, which is the
  329.  * number of arguments actually supplied on the command line.
  330.  *--------------------------------------------------------------------
  331.  */
  332.  
  333. static    int __regargs 
  334. cmdparse (int argc, char **argv)
  335. {
  336.     char *junk = NULL;
  337.     int error = 0;
  338.  
  339.     if (argc <= 0)
  340.     {
  341.         /* Workbench */
  342.         return (-1);
  343.     }
  344.     else if (argc > 10)
  345.     {
  346.         fprintf (stderr,
  347.              "?? Too many arguments\n%s\n%s\n",
  348.              CLI_Help, CLI_Template);
  349.         return (-1);
  350.     }
  351.  
  352.     infile = argv[1];    /* From */
  353.     outfile = argv[2];    /* To */
  354.     if (argv[3])        /* COLSTART */
  355.     {
  356.         colstart = strtol (argv[3], &junk, 10);
  357.         if (junk && *junk)
  358.         {
  359.             fprintf (stderr,
  360.                  "?? Invalid digit \"%c\" for COLSTART\n",
  361.                  *junk);
  362.             error = -1;
  363.         }
  364.     }
  365.     if (argv[4])        /* WIDTH */
  366.     {
  367.         colwidth = strtol (argv[4], &junk, 10);
  368.         if (junk && *junk)
  369.         {
  370.             fprintf (stderr,
  371.                  "?? Invalid digit \"%c\" for WIDTH\n",
  372.                  *junk);
  373.             error = -1;
  374.         }
  375.     }
  376.     if (argv[5])        /* TABSTOP */
  377.     {
  378.         tabstop = strtol (argv[5], &junk, 10);
  379.         if (tabstop < 0)
  380.         {
  381.             fprintf (stderr, "?? Invalid TABSTOP\n" );
  382.             error = -1;
  383.         }
  384.         else if (junk && *junk)
  385.         {
  386.             fprintf (stderr,
  387.                  "?? Invalid digit \"%c\" for TABSTOP\n",
  388.                  *junk);
  389.             error = -1;
  390.         }
  391.     }
  392.     caseflag = (argv[6] != NULL);        /* CASE */
  393.     reverseflag = (argv[7] != NULL);    /* REVERSE */
  394.     stripflag = (argv[8] != NULL);        /* STRIP */
  395.  
  396.     if (argv[9])                /* OPT */
  397.     {
  398.         strupr (argv[9]);
  399.         if (strchr(argv[9],'T') && !tabstop)
  400.             tabstop = 8;
  401.         if (strchr(argv[9],'C'))
  402.             caseflag = TRUE;
  403.         if (strchr(argv[9],'R'))
  404.             reverseflag = TRUE;
  405.         if (strchr(argv[9],'S'))
  406.             stripflag = TRUE;
  407.         if (strchr(argv[9],'X'))
  408.             tabstop = -1;
  409.     }
  410.  
  411.     return (error);
  412. }
  413.  
  414. /*---------------------------------------------------------------------------
  415.  * Initialize a new node to be inserted in the tree.
  416.  *---------------------------------------------------------------------------
  417.  */
  418.  
  419. static    MYNODE * __regargs 
  420. newnode (PCHAR text, ULONG textlen)
  421. {
  422.     PCHAR        ptext;
  423.     MYNODE *    pnew = NULL;
  424.     static AVLNODE    avldummy = {NULL, NULL, 0};
  425.  
  426.     if (ptext = myalloc (textlen + 1))
  427.     {
  428.         if (pnew = myalloc (SZOF_MYNODE))
  429.         {
  430.             strcpy (ptext, text);
  431.             pnew->v.avlnode = avldummy;
  432.             pnew->text = ptext;
  433.             pnew->textlen = textlen;
  434.             NewList (&pnew->chain);
  435.         }
  436.     }
  437.     return (pnew);
  438. }
  439.  
  440. /*---------------------------------------------------------------------------
  441.  *
  442.  *    int cmprtc( keyP, nodeP )
  443.  *        void    *keyP;
  444.  *        AVLNODE    *nodeP;
  445.  *
  446.  *    CMPRTC compares a given key against a key associated
  447.  *    with a node.
  448.  *
  449.  *    keyP    the address of a key (interpreted in
  450.  *        whatever way is applicable)
  451.  *    nodeP    the address of an AVLNODE structure
  452.  *        to which the key should be compared.
  453.  *
  454.  *    It shall return
  455.  *        -1 if keyP is less than the key associated with nodeP key;
  456.  *         0 if they match;
  457.  *        +1 if keyP is greater than the key associated with nodeP.
  458.  *
  459.  *    IMPLEMENTATION NOTE:
  460.  *    For this application, keyP points to a previously-allocated
  461.  *    AVL node.
  462.  *---------------------------------------------------------------------------
  463.  */
  464.  
  465. static    int __regargs 
  466. cmprtc (void *keyP, AVLNODE * nodeP)
  467. {
  468.     MYNODE * kp = (MYNODE *) keyP;
  469.     MYNODE * np = (MYNODE *) nodeP;
  470.     PCHAR ktext = kp->text + colstart;
  471.     PCHAR ntext = np->text + colstart;
  472.     int khastext = (kp->textlen > colstart);
  473.     int nhastext = (np->textlen > colstart);
  474.     int cmp;
  475.  
  476.     /*---------------------------------------------------------------
  477.      * If both lines are long enough, apply the comparison function.
  478.      * If only one line is long enough, it should precede the other.
  479.      * If neither line is long enough, call them equal (for now).
  480.      *---------------------------------------------------------------
  481.      */
  482.  
  483.     if (khastext && nhastext)
  484.         cmp = (*pfnCompare) (ktext, ntext, colwidth);
  485.     else
  486.     {
  487.         /*--------------------------------------
  488.          * k n -> cmp
  489.          * ----------
  490.          * 0 0     0    equal
  491.          * 1 0    -1    key has precedence
  492.          * 0 1     1    node has precedence
  493.          * 1 1    n/a    handled by if(), above
  494.          *--------------------------------------
  495.          */
  496.         cmp = nhastext - khastext;
  497.     }
  498.  
  499.     /*--------------------
  500.      * Return -1, 0, or 1.
  501.      *--------------------
  502.      */
  503.     return (cmp > 0) - (cmp < 0);
  504. }
  505.  
  506. /*---------------------------------------------------------------------------
  507.  *    AVLNODE *mknode( treeP, keyP, dataP, enodeP )
  508.  *        AVLTREE    *treeP;
  509.  *        void    *keyP;
  510.  *        void    *dataP;
  511.  *        AVLNODE    *enodeP;
  512.  *
  513.  *    MKNODE creates a node on behalf of tree insertion.
  514.  *
  515.  *    treeP    the address of the tree description structure
  516.  *    keyP    the address of any key associated with the node
  517.  *    dataP    the address of any data associated with the node
  518.  *    enodeP    the address of any node that already exists in
  519.  *        the tree for keyP.
  520.  *
  521.  *    If enodeP is not NULL, then this routine is being called
  522.  *    to replace the data in an existing node.  It can signal
  523.  *    its unwillingness to do this by returning NULL as its
  524.  *    return value, otherwise it must return the address of the
  525.  *    existing node.  Otherwise (if enodeP is NULL), this
  526.  *    routine should allocate (or otherwise create) a new node
  527.  *    and fill it in.
  528.  *
  529.  *    MKNODE shall return the address of the node constructed,
  530.  *    or NULL if no node was made.
  531.  *
  532.  *    IMPLEMENTATION NOTE:
  533.  *    For this application, keyP points to a previously-allocated
  534.  *    AVL node.
  535.  *---------------------------------------------------------------------------
  536.  */
  537.  
  538. static    AVLNODE * __regargs 
  539. mknode (AVLTREE * treeP, void *keyP, void *dataP, AVLNODE * enodeP)
  540. {
  541.     if (enodeP)
  542.     {
  543.         AddTail (&((MYNODE *) enodeP)->chain, (struct Node *)keyP);
  544.         return ((AVLNODE *) enodeP);
  545.     }
  546.     else
  547.         return ((AVLNODE *) keyP);
  548. }
  549.  
  550. /*---------------------------------------------------------------------------
  551.  *    void rmnode( treeP, nodeP )
  552.  *        AVLTREE    *treeP;
  553.  *        AVLNODE    *nodeP;
  554.  *
  555.  *    RMNODE is called to delete a node and its information.
  556.  *
  557.  *    treeP is the address of the tree description structure;
  558.  *    nodeP is the address of the node to delete.
  559.  *
  560.  *    It is called when a node is removed from a tree; it may
  561.  *    do what it likes and does not return any information.
  562.  *
  563.  *    IMPLEMENTATION NOTE:
  564.  *    For this application, we cannot do anything.
  565.  *---------------------------------------------------------------------------
  566.  */
  567.  
  568. static    void __regargs 
  569. rmnode (AVLTREE * treeP, AVLNODE * nodeP)
  570. {
  571. }
  572.  
  573. /*---------------------------------------------------------------------------
  574.  * Print the tree to stdout (which may have been redirected).
  575.  *---------------------------------------------------------------------------
  576.  */
  577.  
  578. static    void __regargs 
  579. printtree (MYNODE * pnode)
  580. {
  581.     MYNODE    *xp;
  582.  
  583.     if (!pnode)
  584.         return;
  585.  
  586.     /*---------------------------------------------
  587.      * Call ARP function to check for break signal.
  588.      *---------------------------------------------
  589.      */
  590.     CheckBreak (BREAKFLAGS, handlebreak);
  591.  
  592.     if (reverseflag)
  593.     {
  594.         printtree ((MYNODE *) (pnode->v.avlnode.n_rightP));
  595.         while (xp = (MYNODE *) RemTail (&pnode->chain))
  596.             puts(xp->text);
  597.         puts (pnode->text);
  598.         printtree ((MYNODE *) (pnode->v.avlnode.n_leftP));
  599.     }
  600.     else
  601.     {
  602.         printtree ((MYNODE *) (pnode->v.avlnode.n_leftP));
  603.         puts (pnode->text);
  604.         while (xp = (MYNODE *) RemHead (&pnode->chain))
  605.             puts(xp->text);
  606.         printtree ((MYNODE *) (pnode->v.avlnode.n_rightP));
  607.     }
  608. }
  609.  
  610.  
  611. /*---------------------------------------------------------------------------
  612.  * Redirect file handle to named file.
  613.  * Altered from version in REDIRECT.C,
  614.  * so we can use longjmp() rather than exit().
  615.  *---------------------------------------------------------------------------
  616.  */
  617.  
  618. static    FILE *
  619. redirect( char *filename, char *mode, FILE *oldfp, int errlevel )
  620. {
  621.     FILE    *newfp;
  622.  
  623.     if (!mode)
  624.     {
  625.         fprintf( stderr,
  626.              "?? freopen() error for file %s\n", filename );
  627.         longjmp (break_jmp_buf,errlevel);
  628.     }
  629.  
  630.     if ( filename && *filename )
  631.         newfp = freopen( filename, mode, oldfp );
  632.     else
  633.         newfp = oldfp;
  634.  
  635.     if ( newfp == NULL )
  636.     {
  637.         fprintf( stderr,
  638.              "?? Cannot open file %s for %s\n", filename,
  639.              (*mode == 'r') ? "input" :
  640.               (*mode == 'w') ? "output" :
  641.                (*mode == 'a') ? "append" : "(unknown mode)" );
  642.         longjmp (break_jmp_buf,errlevel);
  643.     }
  644.  
  645.     else if ( newfp != oldfp )
  646.     {
  647.         fprintf( stderr,
  648.              "?? freopen() error for file %s\n", filename );
  649.         longjmp (break_jmp_buf,errlevel);
  650.     }
  651.  
  652.     else
  653.         return( newfp );
  654. }
  655.  
  656.